package LinkTest;

public class LinkCount {
    //求链表倒数的最后k个节点，前后指针法
    static class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
      this.val = val;
    }
  }
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        if(pHead==null||k<0){
            return null;
        }
        ListNode fast=pHead;
        ListNode slow=pHead;
        int count=0;
        while(count!=k-1){
            if(fast==null){
                return null;
            }
            fast=fast.next;
            count++;
            if(fast==null){
                return null;
            }
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
    //删除链表的倒数 第k个节点，1.前后指针法2.三指针法，一个指针指向虚拟头节点，两指针指向头结点，其中一指针动n步之后三指针同时动直到之前先动的指针为null，此时原指向
    //虚拟头指针的以为要删除的目标节点的前一个指针，结合另一个指向目标节点的指针删除即可
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        if(head==null||n<=0){
            return null;
        }
        ListNode p=new ListNode(0);
        p.next=head;
        ListNode pre=p;
        ListNode cur=p;
        int i=0;
        while(n!=0){
            pre=pre.next;
            if(pre==null){
                return head;
            }
            n--;
        }
        while(pre.next!=null){
            pre=pre.next;
            cur=cur.next;
        }
        cur.next=cur.next.next;
        return p.next;

    }
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1==null||pHead2==null){
            return null;
        }
        ListNode pre1=pHead1;
        ListNode pre2=pHead2;
        int l1=0;
        int l2=0;
        while(pre1!=null){
            l1++;
            pre1=pre1.next;
        }
        while(pre2!=null){
            l2++;
            pre2=pre2.next;
        }
        pre1=pHead1;
        pre2=pHead2;
        if(l1>l2){
            int l3=l1-l2;
            while(l3-->0){
                pre1=pre1.next;
            }
        }else{
            int l3=l2-l1;
            while(l3-->0){
                pre2=pre2.next;
            }
        }
        while(pHead1!=null&&pHead2!=null){
            if(pHead1==pHead2){
                return pHead1;
            }
            pHead1=pHead1.next;
            pHead2=pHead2.next;

        }
        return null;
    }
}
